/*
    leetcode 704
*/
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int search(vector<int>& nums, int target) {
		int left=0;
		int right=nums.size()-1;
		while(left<=right){
			int middle=left+((right-left)/2);
			if(nums[middle]>target){
				right=middle-1;
			}else if(nums[middle]<target){
				left=middle+1;
			}else{
				return middle;
			}
		} 
		return -1;
    }
};

/* 寻找左侧边界的二分搜索*/
//[1,2,2,2,3] target=2  return:1  说明：目标值2第一次出现是在下标为1的地方
//[2,3,5,7] target=1  return:0  说明：nums中小于1的元素有0个(或：1应该插入的位置是在下标为0的位置)
int left_bound(vector<int>& nums,int target){
    if(nums.size()==0) return -1;
    int left=0;
    int right=nums.size();//注意：这里不减一
    while(left<right){//注意：这里没有=
        int mid=left+(right-left)/2;
        if(nums[mid]==target){
            right=mid;
        }else if(nums[mid]>target){
            right=mid;
        }else if(nums[mid]<target){
            left=mid+1;
        }
    }
    //这里等价于return right;(因为：while终止的条件是left==right)
    return left;
}

//寻找左侧边界的二分搜索plus(如果nums中不存在target,返回-1)
int left_bound2(vector<int>& nums,int target){
    if(nums.size()==0) return -1;
    int left=0;
    int right=nums.size();//注意：这里不减一
    while(left<right){//注意：这里没有=
        int mid=left+(right-left)/2;
        if(nums[mid]==target){
            right=mid;
        }else if(nums[mid]>target){
            right=mid;
        }else if(nums[mid]<target){
            left=mid+1;
        }
    }
    //如果target比所有数都大
    if(left==nums.size()) return -1;
    return nums[left]==target?left:-1;
}
/*
    为什么该算法能够搜索左侧边界？
    当找到target时，不直接返回，而是缩小搜索区间的right，直到到达左侧边界.
*/

//寻找右侧边界的二分查找
int right_bound(vector<int>& nums,int target){
    if(nums.size()==0) return -1;
    int left=0;
    int right=nums.size();
    while(left<right){
        int mid=left+(right-left)/2;
        if(nums[mid]==target){
            left=mid+1;
        }else if(nums[mid]<target){
            left=mid+1;
        }else if(nums[mid]>target){
            right=mid;
        }
    }
    return left-1;
}
//寻找右侧边界的二分查找plus
int right_bound2(vector<int>& nums,int target){
    if(nums.size()==0) return -1;
    int left=0;
    int right=nums.size();
    while(left<right){
        int mid=left+(right-left)/2;
        if(nums[mid]==target){
            left=mid+1;
        }else if(nums[mid]<target){
            left=mid+1;
        }else if(nums[mid]>target){
            right=mid;
        }
    }
    if(left==0) return -1;
    return nums[left-1]==target?(left-1):-1;
}